﻿#light
namespace FunctionalStructures

// Simple One-way List with Random Access 
type public 'a List =
    | Empty                   
    | Node of 'a * 'a List    
   
    (* Helpers *)
    member private this.Head  =  
        match this with
            | Empty -> failwith "Empty stack"
            | Node(hd, tl) -> hd
    member private this.Tail = 
        match this with
            | Empty -> failwith "Empty stack"
            | Node(hd, tl) -> tl
    
    (* Change value at specified position in list *)
    member this.Update index value  =
        match index with
            | 0 -> Node(value, this.Tail)
            | i -> Node(this.Head, this.Tail.Update (i-1) value)

    member this.Count = 
        match this with
            | Empty -> 0
            | Node(a, next) -> next.Count + 1

    member this.Item 
        with get (index:int) =
            match index, this with
                | _, Empty -> failwith "Index out of range"
                | 0, Node(a, next) -> a
                | idx, Node (_, next) -> next.[idx - 1]
    
    member this.Insert index value = 
        match index with
            | 0 -> Node(value, this)
            | i -> Node(this.Head, this.Tail.Insert (i-1) value)

    member this.Cons x = Node(x, this)

    member this.Reverse = 
        let rec reverse destList sourceList =
            match sourceList with
                | Empty -> destList
                | Node(sourceHead, sourceTail) ->
                 reverse (Node(sourceHead, destList)) sourceTail
        reverse Empty this

    (* Concatenation of two list *)
    member this.Concat secondStack =
        match this with
            | Empty -> secondStack
            | this -> Node(this.Head, this.Tail.Concat(secondStack))

    